\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage[UTF8]{ctex}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{tikz}
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{clrscode}
\usepackage{sectsty} % Allows customizing section commands
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usetikzlibrary{graphs}
\usetikzlibrary{shapes.arrows}
\allsectionsfont{\centering \normalfont\scshape} % Make all sections centered, the default font and small caps
%\allsectionsfont{\indent\normalfont\scshape} % Make all sections centered, the default font and small caps
\usepackage{indentfirst}
\setlength{\parindent}{2em}
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage[linesnumbered,boxed,lined,ruled,vlined]{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\usepackage{graphicx}
\usepackage{float}
%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{中国科学院大学}\ \textsc{计算机与控制学院} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge 算法设计与分析第六次作业 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{黎吉国} % Your name

\date{\normalsize\today} % Today's date or a custom date

\begin{document}

\maketitle % Print the title
\newpage

\begin{enumerate}
  \item Interger Programming
  \\
  我们分两步证明整数规划是一个NPC问题：
  \begin{enumerate}
    \item 整数规划是一个NP问题.\\
    假如我们给出一个该问题的“证书”：$x=\{ x_1,x_2,\ldots,x_n \}$，我们需要$O(mn)$的时间来验证是否满足问题的要求。
    所以整数规划是一个NP问题。
    \item 整数规划是NP-hard.\\
    我们这里证明$\text{3-SAT} \le_p \text{Integer-Programming}$.\\
    对于$n$个布尔输入$x_i \in \{ 0,1 \},i=1,2,3,\ldots,n$.由$m$个合取式组成的3-SAT约束式为
    $\phi=C1 \land C2 \land \ldots \land Cn$。我们按照下列规则将这个约束式变成等价的线性规划问题。
    \begin{enumerate}
      \item $x_i \lor x_j \lor x_k \to x_i + x_j + x_k \ge 1$
      \item $x_i \lor \neg x_j \lor x_k \to x_i + (1-x_j) + x_k \ge 1$
    \end{enumerate}
    这样便可以将3-SAT问题规约为一个0-1整数规划问题，而且满足一下条件：
    \begin{enumerate}
    \item 整数规划问题有解时，3-SAT问题也有对应的解。
    \item 整数规划无解时，3-SAT问题也无解。
    \item 对于任意一个3-SAT问题，都可以通过多项式时间将其规约为一个整数规划问题。
    \end{enumerate}
    所以可得$\text{3-SAT} \le_p \text{Integer-Programming}$。
    \item 由前两条可得，整数规划问题属于NPC类。
  \end{enumerate}
  \item Mine-sweeper
  \\
  分两步来证明扫雷问题属于NPC类。
  \begin{enumerate}
    \item 扫雷问题是一个NP问题。\\
    假如图G中有m个节点是已知没有雷且有标签的（周围有多少雷），n-m个节点是未知的，那么对于一个“证书”，
    我们需要$O(m(n-m))$的时间来验证它是否满足要求。所以扫雷问题属于NP类。
    \item 扫雷问题是NP-hard。\\
    这里我们通过证明3-SAT$\le_p$ Mine-weeper来证明扫雷问题是NP-hard。\\
    对于3-SAT约数$\phi=C1 \land C2 \land \ldots \land Cm$，我们通过以下三步将其规约为一个扫雷问题。
    \begin{enumerate}
      \item 添加变量节点X:对于3-SAT问题的n个布尔输入变量，列出2n个节点，分别代表$x_1,\neg x_1,x_2, \neg x_2,\ldots,x_n,\neg x_n$。
      下面对这2n个节点添加约数。
      \item 添加互斥节点D:因为$x_i,\neg x_i$一定只有一个为真，也就是上一步列出的节点中$x_i,\neg x_i$对应的节点必有一个有雷，添加n个节点，
      节点的标签都为1，每个节点同时连上$x_i，\neg x_i,i=1,2,3,\ldots,n$。
      \item 添加约数节点C:对于约束式中的每一项$Ci$，三个布尔变量有且只有一个为真，所以添加m个节点，每个节点的标签为1，节点连接到对应的输入变量节点上。
      列如，$C1=x_1\lor \neg x_2 \lor x_3$，则约束节点$C_1$连接变量节点$x_1,\neg x_2,x_3$。
    \end{enumerate}
    列如，3-SAT问题$\phi=(x_1 \lor x_2 \lor x_3)\land (x_1 \lor \neg x_2 \lor x_3)$规约出的扫雷问题的图为
    \begin{figure}[H]
    \centering
    \includegraphics[width=4in,height=2.5in]{mine-weeper.png}
    \caption{3-SAT问题规约出的扫雷问题实例}
    \label{fig:graph}
    \end{figure}
    同时，归约后的问题满足以下条件：
    \begin{enumerate}
      \item 扫雷问题有解，当且仅当3-SAT问题有解，且解有一一对应关系。
      \item 归约过程只需要$O(n+m)$的时间，其中$n$为布尔变量数目，$m$为约束式中参与合取运算的子式数目。
    \end{enumerate}
    可知 Mine-weeper $\le_p$ 3-SAT.
    \item 由以上两条知，Mine-weeper属于NPC类。
  \end{enumerate}
\end{enumerate}


\end{document}
